//84 柱状图中最大的矩形
//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组


package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class A84LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new A84LargestRectangleInHistogram().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");
        int ans = solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
        System.out.println(ans);
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 单调栈
     * 解答成功:
     * 执行耗时:13 ms,击败了83.81% 的Java用户
     * 内存消耗:40.9 MB,击败了60.87% 的Java用户
     */
    class Solution {
        public int largestRectangleArea(int[] heights) {
            Deque<Integer> stack = new LinkedList<>();
            // 注意这个-1不能乱设置，stack都是先pop再peek，会取到这个-1的
            stack.push(-1);
            int maxarea = 0;
            for (int i = 0; i < heights.length; i++) {
                // 先决条件 && 破坏单调栈性质的数据（当前是个小值）
                while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
//                    // 长度
//                    int len = i - stack.peek();
//                    // heights[stack.peek()]的左边都是矮的，指望不上，右边一直到i都是高的，所以len直接乘上去
//                    maxarea = Math.max(maxarea, heights[stack.peek()] * len);
//                    // 弹出
//                    stack.pop();
                    //  上面语句浓缩成1行
                    maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
                }
                // 经过前面的处理，单调栈性质维护好了，把下标push进去
                stack.push(i);
//                System.out.println(stack.toString());
            }
            // 收尾处理，和for里面的原理是完全一致的
            while (stack.peek() != -1) {
                maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
            }
            return maxarea;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
